package demo.wei;

import java.util.*;

class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();

       /* System.out.println(isPa(12321));
        int[] arr = new int[]{2, 7, 11, 15, 4, 5};
        System.out.println(Arrays.toString(twoSum(arr, 9)));

        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(5);

        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);

        ListNode resultNode = addTwoNumbers(l1, l2);
        System.out.println(resultNode);

        System.out.println(solution.longestPalindrome("babad"));
        System.out.println(Integer.MAX_VALUE);
        System.out.println(reverse(1463847412));

        ListNode ln1 = new ListNode(1);
        ln1.next = new ListNode(2);
        ln1.next.next = new ListNode(3);
        ln1.next.next.next = new ListNode(4);
        ln1.next.next.next.next = new ListNode(5);
        ln1.next.next.next.next.next = new ListNode(6);
        removeNthFromEnd(ln1, 1);

        System.out.println(solution.longestCommonPrefix(new String[]{"flower", "flow", "flow12313"}));

        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(6);
        printNode(reverseKNodes1(head, 2));

        Node n1 = new Node(1);
        n1.next = new Node(2);
        n1.next.next = new Node(2);
        n1.next.next.next = new Node(3);
        n1.next.next.next.next = new Node(3);
        n1.next.next.next.next.next = new Node(4);
        printSNode(n1);
        removeRep1(n1);
        printSNode(n1);

        System.out.println();
        System.out.println("removeElement = " + removeElement2(new int[]{2, 3, 3, 4, 5, 6, 3}, 3));

        Map<String, String> map = new HashMap<String, String>();
        map.put("1", "cxx1");
        map.put("2", "cxx2");
        System.out.println(map.getOrDefault("3", "-1"));

        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        System.out.println(solution.groupAnagrams(strs));
        System.out.println(solution.groupAnagrams2(strs));

        //System.out.println(solution.permute(new int[]{1, 2, 3}));

        System.out.println(solution.permute(new int[]{1, 2, 3}));*/

        System.out.println(solution.maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));

        int[][] intervals = new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        System.out.println(solution.merge(intervals));

        System.out.println(solution.isPowerOfTwo(16));

        System.out.println(solution.combine(4, 2));
    }

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> tmp = new ArrayList<Integer>();
        dfs(res, tmp, n, k, 1);
        return res;
    }

    public void dfs(List<List<Integer>> res, List<Integer> tmp, int n, int k, int m) {
        if (k == 0) {
            res.add(new ArrayList<Integer>(tmp));
            return;
        }
        for (int i = m; i <= n; i++) {
            tmp.add(i);
            dfs(res, tmp, n, k - 1, i + 1);
            tmp.remove(tmp.size() - 1);
        }
    }

    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & -n) == n;
    }

    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }

    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
            System.out.print("pre = " + pre + "  maxAns = " + maxAns);
            System.out.println();
        }
        return maxAns;
    }

    //回溯法
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> listList = new ArrayList<List<Integer>>();
        permute(nums, listList, new ArrayList<Integer>());
        return listList;
    }

    public void permute(int[] nums, List<List<Integer>> listList, List<Integer> list) {
        int n = nums.length;
        if (list.size() == n) {
            listList.add(new ArrayList<>(list));
        }

        for (int i = 0; i < n; i++) {
            if (list.contains(nums[i])) {
                continue;
            }

            list.add(nums[i]);
            permute(nums, listList, list);
            list.remove(list.size() - 1);
        }
    }


    public void permute3(int[] nums, List<List<Integer>> listList, List<Integer> list) {
        int n = nums.length;
        if (list.size() == n) {
            listList.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < n; i++) {
            if (list.contains(nums[i])) {
                continue;
            }
            list.add(nums[i]);
            permute(nums, listList, list);
            list.remove(list.size() - 1);
        }
    }

    public List<List<Integer>> permute2(int[] nums) {
        int len = nums.length;
        // 使用一个动态数组保存所有可能的全排列
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        boolean[] used = new boolean[len];
        Deque<Integer> path = new ArrayDeque<>(len);

        dfs(nums, len, 0, path, used, res);
        return res;
    }

    private void dfs(int[] nums, int len, int depth,
                     Deque<Integer> path, boolean[] used,
                     List<List<Integer>> res) {
        if (depth == len) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < len; i++) {
            if (!used[i]) {
                path.addLast(nums[i]);
                used[i] = true;

                System.out.println("  递归之前 => " + path);
                dfs(nums, len, depth + 1, path, used, res);

                used[i] = false;
                path.removeLast();
                System.out.println("递归之后 => " + path);
            }
        }
    }

    //哈希法
    public List<List<String>> groupAnagrams2(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            int[] hashtable = new int[26];
            for (char c : str.toCharArray()) {
                hashtable[c - 'a']++;
            }

            StringBuffer sb = new StringBuffer();
            for (int count : hashtable) {
                sb.append("#");
                sb.append(count);
            }

            String key = new String(sb.toString());
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }

        return new ArrayList<List<String>>(map.values());
    }

    //排序法
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (int i = 0; i < strs.length; i++) {
            char[] chars = strs[i].toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(strs[i]);
            map.put(key, list);
        }

        return new ArrayList<List<String>>(map.values());
    }

    //2334563
    //2634533
    //2654333
    public static int removeElement2(int[] nums, int val) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int l = 0;
        int r = nums.length - 1;
        while (l < r) {
            while (l < r && nums[l] != val) {
                l++;
            }

            while (l < r && nums[r] == val) {
                r--;
            }

            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
            System.out.println(Arrays.toString(nums));
        }

        return nums[l] == val ? l : l + 1;
    }

    public static int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }

    public static int fei2(int n) {
        if (n < 1) {
            return -1;
        }

        int[] arr = new int[n + 1];
        arr[1] = 1;
        arr[2] = 1;

        for (int i = 3; i <= n; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }

        return arr[n];
    }

    public static int fei1(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }

        return fei1(n - 1) + fei1(n - 2);
    }

    public static void removeRep1(Node head) {
        if (head == null) {
            return;
        }

        HashSet<Integer> set = new HashSet<Integer>();
        Node pre = head;
        Node cur = head.next;
        set.add(head.value);
        while (cur != null) {
            if (set.contains(cur.value)) {
                pre.next = cur.next;
            } else {
                set.add(cur.value);
                pre = cur;
            }
            cur = cur.next;
        }
    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 使用带头结点的链表解决问题
        // 待输出链表的头部
        ListNode head = new ListNode();

        // 待输出链表的 last 结点
        ListNode last = head;
        while (l1 != null && l2 != null) {
            if (l1.val > l2.val) {
                last.next = l2;
                l2 = l2.next;
            } else {
                last.next = l1;
                l1 = l1.next;
            }
            last = last.next;
        }

        // l1 或 l2 可能还有剩余结点没有合并，
        // 由于从上面的 while 循环中退出， 那么链表 l1 和 l2 至少有一个已经遍历结束
        if (l1 != null) last.next = l1;
        if (l2 != null) last.next = l2;

        return head.next;

    }

    public static ListNode reverseKNodes1(ListNode head, int k) {
        if (k < 2) {
            return head;
        }

        Stack<ListNode> stack = new Stack<>();
        ListNode newHead = head;
        ListNode cur = head;
        ListNode pre = null;
        ListNode next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = null;
            stack.push(cur);
            if (stack.size() == k) {
                pre = resgin1(stack, pre, next);
                newHead = newHead == head ? cur : newHead;
                printNode(newHead);
            }
            cur = next;
        }
        return newHead;
    }

    public static ListNode resgin1(Stack<ListNode> stack, ListNode left, ListNode right) {
        ListNode cur = stack.pop();
        if (left != null) {
            left.next = cur;
        }

        while (!stack.isEmpty()) {
            ListNode next = stack.pop();
            cur.next = next;
            cur = next;
        }
        cur.next = right;
        return cur;
    }


    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode hair = new ListNode(0);
        hair.next = head;
        ListNode pre = hair;

        while (head != null) {
            ListNode tail = pre;
            // 查看剩余部分长度是否大于等于 k
            for (int i = 0; i < k; ++i) {
                tail = tail.next;
                if (tail == null) {
                    return hair.next;
                }
            }
            ListNode nex = tail.next;
            ListNode[] reverse = myReverse(head, tail);
            head = reverse[0];
            tail = reverse[1];
            // 把子链表重新接回原链表
            pre.next = head;
            tail.next = nex;
            pre = tail;
            head = tail.next;
        }

        return hair.next;
    }

    public static ListNode[] myReverse(ListNode head, ListNode tail) {
        ListNode prev = tail.next;
        ListNode p = head;
        while (prev != tail) {
            ListNode next = p.next;
            p.next = prev;
            prev = p;
            p = next;
        }
        return new ListNode[]{tail, head};
    }

    public static void printSNode(Node head) {
        System.out.println();
        while (head != null) {
            System.out.print(head.value);
            head = head.next;
        }
    }

    public static void printNode(ListNode head) {
        System.out.println();
        while (head != null) {
            System.out.print(head.val);
            head = head.next;
        }
    }

    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return null;
        }

        int length = strs[0].length();
        int count = strs.length;
        for (int i = 0; i < length; i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < count; j++) {
                if (i == strs[j].length() || c != strs[j].charAt(i)) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }

    //通过快慢指针来解决，类似于你要删除中间元素的题
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        //定义一个伪节点，用于返回结果
        ListNode dumpy = new ListNode(0);
        dumpy.next = head;
        //定义一个快指针,指向伪节点，用于遍历链表
        ListNode prev = dumpy;
        //定一个慢指针，
        ListNode tail = dumpy;
        //让快指针先移动 n 步
        while (n > 0) {
            prev = prev.next;
            n--;
        }
        //只要快指针不指向空，就继续循环
        while (prev.next != null) {
            //让快慢指针同时移动
            tail = tail.next;
            prev = prev.next;
        }
        //这时慢指针移动到的位置就是，要删除节点的前一个节点
        //所以只要删除当前节点的下一个节点
        tail.next = tail.next.next;
        //返回为指针指向的头节点
        return dumpy.next;
    }

    public static int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            if (rev < Integer.MIN_VALUE / 10 || rev > Integer.MAX_VALUE / 10) {
                return 0;
            }

            int digit = x % 10;
            x = x / 10;
            rev = rev * 10 + digit;
        }
        return rev;
    }

    /**
     * 最长回文子串
     *
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {

        String result = "";

        boolean table[][] = new boolean[s.length()][s.length()];

        // length === 1;
        for (int i = 0; i < table.length; i++) {
            table[i][i] = true;
            result = s.substring(i, i + 1);
        }

        // length === 2;
        for (int i = 0; i < table.length - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                table[i][i + 1] = true;
                result = s.substring(i, i + 2);
            } else {
                table[i][i + 1] = false;
            }
        }

        // length > 2;
        for (int len = 3; len <= table.length; len++) {
            for (int i = 0; i + len <= table.length; i++) {
                char front = s.charAt(i);
                char end = s.charAt(i + len - 1);
                if (front == end) {
                    table[i][i + len - 1] = table[i + 1][i + len - 2];
                } else {
                    table[i][i + len - 1] = false;
                }
                if (table[i][i + len - 1]) {
                    result = s.substring(i, i + len);
                }
            }
        }

        return result;
    }

    //l1 = [2,4,5], l2 = [5,6,4]
    //542 + 465 = 1007.
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0; // 余数
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }

    private static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    '}';
        }
    }

    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);

        }
        return new int[0];
    }

    public static boolean isPa(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int revertedNumber = 0;
        //1 1232
        //12 123
        //123 12
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x = x / 10;
        }

        return x == revertedNumber || x == revertedNumber / 10;
    }


    public static boolean isPalindrome(int x) {
        // 特殊情况：
        // 如上所述，当 x < 0 时，x 不是回文数。
        // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
        // 则其第一位数字也应该是 0
        // 只有 0 满足这一属性
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x = x / 10;
        }

        // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
        // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
        // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
        return x == revertedNumber || x == revertedNumber / 10;
    }

    private static class Node {
        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }
}

